# 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
#  每行中的整数从左到右按升序排列。
#  每行的第一个整数大于前一行的最后一个整数。
#
#  示例 1：
# 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
# 输出：true
#
#  示例 2：
# 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
# 输出：false
from typing import List


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        """
        二分查找
        将每一行拼接在上一行的末尾，则会得到一个升序数组arr
        两者的对应关系为：matrix[i][j] = arr[n * i + j]
        :param matrix:
        :param target:
        :return:
        """
        rows, columns = len(matrix), len(matrix[0])
        left, right = 0, rows * columns - 1
        while left <= right:
            mid = left + (right - left) // 2
            i, j = mid // columns, mid % columns
            if matrix[i][j] == target:
                return True
            elif target > matrix[i][j]:
                left = mid + 1
            else:
                right = mid - 1
        return False


if __name__ == "__main__":
    matrix = [
        [1, 3, 5, 7],
        [10, 11, 16, 20],
        [23, 30, 34, 60]]
    target = 23
    print(Solution().searchMatrix(matrix, target))
